Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Arithmetic Slices II - Subsequence

Problem Statement

Given an array of integers nums, return the number of arithmetic subsequences of nums.

If any integer array consists of at least three elements and if the difference between any two consecutive elements is the same, it is called arithmetic.

  • For example [3, 6, 9, 12] is arithmetic sequences.

A subsequence of an array is a sequence that can be formed by eliminating some or no elements from the array.

Examples

  1. Example 1:

    • Input: nums = [1, 2, 3, 4]
    • Expected Output: 3
    • Justification: The possible arithmetic subsequences are [1, 2, 3], [2, 3, 4], and [1, 2, 3, 4]. Each has a common difference of 1. These are the only subsequences that meet the criteria.
  2. Example 2:

    • Input: nums = [9, 4, 7, 2, 10]
    • Expected Output: 1
    • Justification: The possible arithmetic subsequence is [4, 7, 10]. It has a consistent difference between consecutive elements, which is 3.
  3. Example 3:

    • Input: nums = [3, 6, 9, 12, 15]
    • Expected Output: 7
    • Justification: The arithmetic subsequences are [3, 6, 9], [6, 9, 12], [9, 12, 15], [3, 6, 9, 12], [6, 9, 12, 15], [3, 6, 9, 12, 15], and [3, 9, 15].

Solution

To solve this problem, we'll use dynamic programming combined with hashing. The key idea is to track the number of subsequences ending at each index with a specific common difference. This method is effective because it allows us to efficiently update and count subsequences as we iterate through the array, leveraging previous computations.

The approach works well because it breaks down the problem into smaller, manageable sub-problems. Each sub-problem involves calculating the number of arithmetic subsequences ending at a particular element, which we then aggregate for the final count. By using a hash map to store these counts based on their common differences, we can update and retrieve them in constant time, making this method highly efficient for the task.

Step-by-Step Algorithm

  1. Initialization: Create a list of hash maps, one for each element in the input array. Each hash map will track the count of arithmetic subsequences ending at that element, keyed by their common difference.

  2. Iterate Through the Array: For each element nums[i] in the input array, starting from the second element, perform the following steps:

    • Initialize an empty hash map for nums[i].
    • Iterate through all previous elements nums[j] where j < i.
      • Calculate the difference d = nums[i] - nums[j].
      • Retrieve the count of subsequences ending at j with difference d, denoted as countAtJ. If no such count exists, consider countAtJ to be 0.
      • Retrieve the count of subsequences ending at i with difference d, denoted as countAtI. If no such count exists, consider countAtI to be 0.
      • Update the count at i for difference d by adding countAtJ + 1 to countAtI. The "+1" accounts for the new subsequence formed by nums[j] and nums[i].
      • If j had one or more subsequences ending with it with the same difference d, add countAtJ to the total count of valid arithmetic subsequences.
  3. Aggregate the Total Count: The total count of arithmetic subsequences with at least three elements is accumulated during the iteration. This is the final answer.

  4. Return the Total Count: Return the accumulated total count of valid arithmetic subsequences.

Algorithm Walkthrough

Let's consider the input: nums = [3, 6, 9, 12, 15].

  1. Initialization:

    • Begin without any previous comparisons, as the algorithm starts with the second element for comparisons.
  2. First Element: 3

    • No comparisons are made. HashMaps are still empty.
  3. Second Element: 6

    • Comparing with first element (3):
      • Difference d = 6 - 3 = 3.
      • Update HashMap at index 1: {3: 1}.
    • HashMap Visualization:
      • Index 0: {}
      • Index 1: {3: 1}
  4. Third Element: 9

    • Comparing with first element (3):
      • Difference d = 9 - 3 = 6.
      • Update hashmap with d = 6.
    • Comparing with second element (6):
      • Difference d = 9 - 6 = 3.
      • There's 1 subsequence ending at 6 with this difference.
      • Update HashMap at index 2: {3: 2} (1 existing + 1 new).
      • Total count increases by 1 (for [3, 6, 9]).
      • TotalCount = 1.
    • HashMap Visualization:
      • Index 0: {}
      • Index 1: {3: 1}
      • Index 2: {3: 2, 6: 1}
  5. Fourth Element: 12

    • Comparing with first element (3):
      • Difference d = 12 - 3 = 9.
      • Update hashmap with d = 9.
    • Comparing with second element (6):
      • Difference d = 12 - 6 = 6.
      • Update hashmap with d = 6.
    • Comparing with third element (9):
      • Difference d = 12 - 9 = 3.
      • There are 2 subsequences ending at 9 with this difference.
      • Update HashMap at index 3: {3: 3} (2 existing + 1 new).
      • Total count increases by 2 (for [6, 9, 12] and [3, 6, 9, 12]).
      • TotalCount = 3.
    • HashMap Visualization:
      • Index 0: {}
      • Index 1: {3: 1}
      • Index 2: {3: 2, 6: 1}
      • Index 3: {3: 3, 6: 1, 9: 1}
  6. Fifth Element: 15

    • Comparing with first element (3):
      • Difference d = 15 - 3 = 12.
      • Update hashmap with d = 12.
    • Comparing with second element (6):
      • Difference d = 15 - 6 = 9.
      • Update hashmap with d = 9.
    • Comparing with third element (9):
      • Difference d = 15 - 9 = 6.
      • There are 1 subsequences ending at 9 with this difference.
      • Update HashMap at index 4: {6: 2} (1 existing + 1 new).
      • Total count increases by 1 (for [3, 9, 15]).
      • TotalCount = 4.
    • Comparing with fourth element (12):
      • Difference d = 15 - 12 = 3.
      • There are 3 subsequences ending at 12 with this difference.
      • Update HashMap at index 4: {3: 4} (3 existing + 1 new).
      • Total count increases by 3 (for [9, 12, 15], [6, 9, 12, 15], and [3, 6, 9, 12, 15]).
      • TotalCount = 7.
    • HashMap Visualization:
      • Index 0: {}
      • Index 1: {3: 1}
      • Index 2: {3: 2, 6: 1}
      • Index 3: {3: 3, 6: 1, 9: 1}
      • Index 4: {3: 4, 9: 1, 12: 1, 6: 2}
  7. Final Consideration:

    • The total count thus far is 7 for explicitly identified subsequences.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the input array. This is because there are two nested loops:

  • The outer loop runs (n) times, once for each element in the array.
  • The inner loop runs for each pair of elements in the array, leading to iterations in total, which simplifies to .

Space Complexity

The space complexity is due to the usage of a list of hash maps, where each hash map can potentially store up to (n-1) entries (representing different arithmetic differences found so far). In the worst case, where every pair of elements in the array has a unique difference, this structure could store ) entries.

Arithmetic Slices II - Subsequence (hard)
Burst Balloons (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity